package net.cloudsun.graph.puzzle;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 排列树
 *
 * @author Ryan
 * @since 1.0
 */
public class ArrangementTree<T> {
    /*
     * 怎么生成呢？ 如何排列组合？
     * 难道写9层循环？
     * 对于0~8这9个位置
     * 每个位置拿从deque中拿一个数字
     * 现在首要的问题，是生成所有的排列组合
     * 按这个顺序
     * 0 1 2 3 4 5 6 7 8
     * 0 1 2 3 4 5 6 8 7
     * 0 1 2 3 4 5 7 6 8
     * 0 1 2 3 4 5 7 8 6
     * 0 1 2 3 4 5 8 6 9
     * 0 1 2 3 4 5 8 9 6
     * 其实这是一颗树
     * 树根上分出9个叉
     * 然后每个叉上分出8个叉
     * 一直到最后只有一个叉
     * 既然是树，就可以随便使用一种遍历方法
     */
    public static class Node<T> {
        private Node<T> parent;
        private T value;

        public Node() {
        }

        public Node(T value) {
            this.value = value;
        }

        public Node(Node<T> parent, T value) {
            this.parent = parent;
            this.value = value;
        }
    }


    /**
     * 所有的排列
     */
    private List<List<T>> arrangements;
    private T[] elements;

    public ArrangementTree(T[] elements) {
        this.elements = elements;
        // 进行构造
        createArrangements(elements);
    }

    public List<List<T>> getArrangements() {
        return arrangements;
    }

    private void createArrangements(T[] elements) {
        int factorial = factorial(elements.length);
        arrangements = new ArrayList<>(factorial);
        Deque<Node<T>> deque = new LinkedList<>();
        Node<T> root = new Node<>();
        deque.offer(root);
        // 计算阶乘
        // 用宽度搜索进行遍历
        while (!deque.isEmpty()) {
            Node<T> tNode = deque.poll();
            List<Node<T>> children = getChildren(tNode);
            if (children.isEmpty()) {
                // 生成排列组合
                List<T> result = getArrangement(tNode);
                arrangements.add(result);
            } else {
                children.forEach(deque::add);
            }
        }
    }

    private List<T> getArrangement(Node<T> tNode) {
        ArrayList<T> list = new ArrayList<>(elements.length);
        for (Node<T> pointer = tNode; pointer.parent != null; pointer = pointer.parent) {
            if (pointer.value != null) {
                list.add(pointer.value);
            }
        }
        return list;
    }

    private List<Node<T>> getChildren(Node<T> tNode) {
        // 往上遍历

        Set<T> toRemove = new HashSet<>();
        for (Node<T> pointer = tNode; pointer.parent != null; pointer = pointer.parent) {
            if (pointer.value != null) {
                toRemove.add(pointer.value);
            }
        }
        ArrayList<T> all = new ArrayList<>(Arrays.asList(elements));
        all.removeAll(toRemove);
        return createNodes(tNode,all);
    }

    private List<Node<T>> createNodes(Node<T> parent, ArrayList<T> all) {
        return all.stream().map(x -> new Node<T>(parent, x)).collect(Collectors.toList());
    }

    public static int factorial(int x) {
        int r = 1;
        for (int i = x; i > 1; i--) {
            r *= i;
        }
        return r;
    }
}
